Almost all microprocessors have a load-store architecture in which values are loaded from memory into registers, operations are performed on values loaded in the registers, and the resulting values are again stored into memory. Register allocation, which is typically a function of compilation systems, determines the values that may access the registers of a computer system during any point in the execution of a program. Accordingly, register allocation is an important technique of compiler optimization because the number of computer registers is limited and because register operations are performed faster than memory loads and stores. Register allocation is discussed with reference to Advanced Compiler Design and Implementation, Steven S. Muchnick, 1997.
Some methods for optimizing register allocation limit the allocation of values to computer registers, to periods when an instruction associated with the value is live. It will be appreciated that a code instruction may be associated with a value, and the value is referred to as "live" during the time period in which the value may be executed. Also, the register accessed by the value is termed a "live register" during the period that the value is live. The range of code instructions in which the value is live is referred to as a live range of the value. While a value is live it is desirable to allocate a register to the value to enable instruction processing to continue without storing the value in memory, and the allocated register may be referred to as a live register. Values may reside in virtual registers and virtual registers may represent hardware registers. As used herein the phrase computer registers, represents those registers that are visible to the software developer.
Prior register allocation solutions included recording a history of read instructions and write instructions and searching the recorded events to find the maximum number of live registers, sometimes referred to as the maximum pressure point, at a particular point in the execution of the program. Therefore, the comprehensive read instruction and write instruction history related to the execution of a program must be stored, and that results in a large amount of time required for compiler optimization. It will be appreciated by those skilled in the art, that compiler optimization uses the value of the maximum number of live registers to efficiently manager register allocation.
Since the number of samples to be searched is large, the associated large amount of computing resources and searching time has inhibited improvements in compiler optimization. As known to those skilled in the art, compiler optimization solutions that increase the computer overhead necessary for compilation, reduce the usefulness of the optimization solution and reduce the productivity of software development engineers. This reduction in productivity and increase in computer system requirements has limited further improvement of software development techniques.